#include<stdio.h>
long long int factor(long long int n)
{
    long long int i,count=0;
    for(i=1;i<=n;i++)
    {
        if(n%i==0)
        count++;
    }
    return count;
}
long long C(int N, int M) {
	long long sum = 1;
	for (int i = 1; i <= M; i++) 
	{
		sum = sum * (N - M + i) / i;
	}
	return sum;
}

int main()
{
    long long int t,n,m;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        long long int x=factor(n);
        printf("%lld\n",(C(x,2*m)+x)%998244353);
    }
    return 0;
}